Event data (or logs) is widely available in many application domains, such as systems management, process control, and manufacturing. For example, in systems management, which typically relates to the management of distributed computing and/or communication networks, events are generated from a variety of sources, such as network devices, application servers, and system management software. Event logs often record important temporal activities that provide important information resources. As one example, a network device uses a log file to record its important status changes, such as “cold start,” “port up/down,” “link up/down.” The device log file can be used for problem diagnosis and determination. As another example, an application server, such as web servers, mail servers, and DNS (domain name system) servers, usually maintains a service access log recording client access activities. These log files provide a basis for understanding server workload and client access behaviors. As the third example, system management software, such as Netview (available from IBM Corporation) and TEC (available from Tivoli), keep track of all messages sent by managed nodes in either a database or a log file. These system events are crucial for maintaining the normal operations of a system.
Temporal, periodic behavior is common in event data. This is discussed in B. Ozden et al., “Cyclic association rules,” Int. Conf. Data Engineering, pp. 412–421, 1998; and J. Han et al., “Efficient mining of partially periodic patterns in time series database,” Int. Conf. Data Engineering, 1999, the disclosures of which are incorporated by reference herein. For example, our study of event logs in a production computer network found that over 50% of the events can be explained by periodic temporal patterns. An example periodic temporal pattern in computer networks might consist of five repetitions every 30 seconds of a port-down event followed by a port-up event, which in turn is followed by a random gap until the next five repetitions of these events. Two factors contribute to this phenomenon. The first consideration relates to monitoring. When a managed element emits a high severity event, the management server often initiates periodic monitoring of key resources, e.g., router central processing unit (CPU) utilization. The second consideration is a consequence of routine tasks, such as rebooting print servers every morning or backing up data every week.
Mining such periodic patterns can provide great value. Our experience with analyzing events in computer networks is that periodic patterns often lead to actionable insights. There are two reasons for this conclusion. First, a periodic pattern indicates something persistent and predictable. Thus, there is value in identifying and characterizing the periodicity. Second, the period itself often provides a signature of the underlying phenomena, thereby facilitating diagnosis. In either case, patterns with a very low support (number of occurrences in the data) are often of great interest. For example, we found a one-day periodic pattern due to a periodic port-scan. Although this pattern only happens three times in a three-day log, it provides a strong indication of a security intrusion.
Unfortunately, mining such periodic patterns is complicated by several factors.
(1) Periodic behavior is not necessarily persistent. For example, in complex networks, periodic monitoring is initiated when an exception occurs (e.g., CPU utilization exceeds a threshold) and stops once the exceptional situation is no longer present. During the monitoring interval or “on” segment, the monitoring request and its response occur periodically. The “off” segment consists of a random gap in the periodicity until another exceptional situation initiates periodic monitoring. This makes it difficult to apply well established techniques such as fast Fourier transforms.
(2) There may be time shifts or imprecisions due to network delays, lack of clock synchronization, and rounding errors.
(3) Period lengths are not known in advance. This means that either an exhaustive search is required or there must be a way to infer the periods. Further, periods may span a wide range, from milliseconds to days.
(4) The number of occurrences of a periodic pattern typically depends on the period. For example, a pattern with a period of one day has, at most, seven occurrences in a week, while one minute period may have as many as 1440 occurrences. Thus, mining patterns with longer periods requires adjusting support levels. In particular, mining patterns with low support greatly increases computational requirements in existing approaches to discovering temporal associations.
Existing work does not address key characteristics of these patterns, especially: the presence of noise, time shifts, the fact that periods may not be known in advance, and the need to have computationally efficient schemes for finding large patterns with low support. This invention develops effective, yet scaleable algorithms for mining such patterns that take these considerations into account.
Sequential mining has been studied extensively, especially in domains such as event correlation in telecommunication networks (see, e.g., H. Mannila et al., “Discovery of frequent episodes in event sequences,” Data Mining and Knowledge Discovery, 1(3), 1997, the disclosure of which is incorporated by reference herein), web log analysis (see, e.g., R. Cooley et al, “Web mining: Information and pattern discovery on the world wide web,” Proceedings of the 9th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'97), 1997, the disclosure of which is incorporated by reference herein), and transactions processing (see, e.g., R. Agrawal et al., “Mining association rules between sets of items in large databases,” Proc. of VLDB, pp. 207–216, 1993; and R. Srikant et al., “Mining sequential patterns: Generalizations and performance improvements,” Proc. of the Fifth Int'l Conference on Extending Database Technology (EDBT), Avignon, France, 1996, the disclosures of which are incorporated by reference herein). One theme with respect to this existing work is to discover frequent temporal associations, i.e., finding a set of events that co-occur within a predefined time window. However, these existing approaches can not be used directly for finding periodic patterns.
There has also been recent work in identifying periodic behaviors, see, e.g., the above-referenced J. Han et al. article and the B. Ozden et al. article. Ozden et al. study mining of cyclic association rules for full periodicities, i.e., patterns that are present at each cycle. As noted earlier, this is quite restrictive since periodicity may occur only intermittently. Han et al. studies partially periodic patterns. Han et al. defines partially periodic patterns for sequence data through non-overlapped segmentations of sequences. Their focus is symbol (or discrete) sequences, not time-based sequences. Further, they assume that period lengths are known in advance or that it is reasonable to employ an exhaustive search to find the periods. The invention makes neither assumption. In addition, none of these studies consider the effect of noise, i.e., random occurrences of events of the same type as those in the periodic pattern. Nor do these studies address the problem of time shifts or imperfections in the periodicity.
The fast Fourier transform (FFT) is a well developed technique for identifying periods. However, there are two problems with the use of this technique. First, while the FFT is effective for finding a wide range of periods, it does not cope well with random off-segments in partially periodic patterns as will be explained in accordance with the present invention. Further, the computational efficiency of FFT depends on the range of time scales. The computational complexity of FFT is O(T log T), where T is the number of time units. This is undesirable for sparse events with periodicities over a wide range of time-scales, which is often the case in network management. For example, although there may be hundreds of thousands of events in a month, there are over one billion milliseconds.
Accordingly, there is a need for techniques for discovering partially periodic event patterns which take into account one or more of the following: (i) the presence of noise; (ii) time shifts or imprecisions; (iii) the fact that periods may not be known in advance; and (iv) the need to have computationally efficient schemes for finding large patterns with low support, as well as other considerations.